package com.yoshino.leetcode.oneHundred.threeteenth;

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] exchange(int[] nums) {
        if (nums.length == 0) {
            return nums;
        }
        int[] res = new int[nums.length];
        int first = 0, end = res.length - 1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 0) {
                res[end--] = nums[i];
            } else {
                res[first++] = nums[i];
            }
        }
        return res;
    }

    public int[] twoSum2(int[] nums, int target) {
        if (nums.length < 2 || target < nums[0]) {
            return new int[2];
        }
        Set<Integer> sets = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            sets.add(nums[i]);
        }
        int temp;
        for (int i = 0; i < nums.length; i++) {
            temp = nums[i];
            if (sets.contains(target - temp)) {
                return new int[]{temp, target - temp};
            }
        }
        return new int[2];
    }

    public int[] twoSum(int[] nums, int target) {
        if (nums.length < 2 || target < nums[0]) {
            return new int[2];
        }
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = ((r - l) >> 1) + l;
            if (nums[mid] > target / 2) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        l--;
        r--;
        while (l >= 0 && r < nums.length) {
            if (l != r && nums[l] + nums[r] == target) {
                return new int[]{nums[l], nums[r]};
            } else if (nums[l] + nums[r] > target) {
                l--;
            } else {
                r++;
            }
        }
        return new int[2];
    }

    public String reverseWords(String s) {
        if (s.length() < 1) {
            return "";
        }
        int end = s.length(), first = end - 1;
        StringBuilder sb = new StringBuilder();
        while (first >= 0) {
            if (s.charAt(first) == ' ') {
                if (first + 1 != end) {
                    sb.append(s.substring(first, end));
                    sb.append(" ");
                }
                end = first;
            }
            first--;
        }
        if (end != 0) {
            sb.append(s.substring(0, end));
        } else {
            if (sb.length() == 0) {
                return "";
            }
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }
}